{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #tree #array #divide-and-conquer #binary-tree #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #树 #数组 #分治 #二叉树 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: constructMaximumBinaryTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个不重复的整数数组&nbsp;<code>nums</code> 。&nbsp;<strong>最大二叉树</strong>&nbsp;可以用下面的算法从&nbsp;<code>nums</code> 递归地构建:</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>创建一个根节点，其值为&nbsp;<code>nums</code> 中的最大值。</li>\n",
    "\t<li>递归地在最大值&nbsp;<strong>左边</strong>&nbsp;的&nbsp;<strong>子数组前缀上</strong>&nbsp;构建左子树。</li>\n",
    "\t<li>递归地在最大值 <strong>右边</strong> 的&nbsp;<strong>子数组后缀上</strong>&nbsp;构建右子树。</li>\n",
    "</ol>\n",
    "\n",
    "<p>返回&nbsp;<em><code>nums</code> 构建的 </em><strong><em>最大二叉树</em> </strong>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/12/24/tree1.jpg\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,2,1,6,0,5]\n",
    "<strong>输出：</strong>[6,3,5,null,2,0,null,null,1]\n",
    "<strong>解释：</strong>递归调用如下所示：\n",
    "- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。\n",
    "    - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。\n",
    "        - 空数组，无子节点。\n",
    "        - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。\n",
    "            - 空数组，无子节点。\n",
    "            - 只有一个元素，所以子节点是一个值为 1 的节点。\n",
    "    - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。\n",
    "        - 只有一个元素，所以子节点是一个值为 0 的节点。\n",
    "        - 空数组，无子节点。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/12/24/tree2.jpg\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,2,1]\n",
    "<strong>输出：</strong>[3,null,2,null,1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 1000</code></li>\n",
    "\t<li><code>nums</code> 中的所有整数 <strong>互不相同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-binary-tree](https://leetcode.cn/problems/maximum-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-binary-tree](https://leetcode.cn/problems/maximum-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,2,1,6,0,5]', '[3,2,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def insertIntoMaxTree(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        def constructMaximumBinaryTree(nums: List[int]) -> Optional[TreeNode]:\n",
    "            if nums == []:\n",
    "                return None\n",
    "            else:\n",
    "                a=nums.index(max(nums))\n",
    "                curroot=TreeNode(val=nums[a])\n",
    "                leftnums=nums[:a]\n",
    "                rightnums=nums[a+1:]\n",
    "                curroot.left=constructMaximumBinaryTree(leftnums)\n",
    "                curroot.right=constructMaximumBinaryTree(rightnums)\n",
    "                return curroot\n",
    "        nums=[]\n",
    "        def dfs(root1):\n",
    "            if root1 is None:\n",
    "                return \n",
    "            else:\n",
    "                dfs(root1.left)\n",
    "                nums.append(root1.val)\n",
    "                dfs(root1.right)\n",
    "        dfs(root)\n",
    "        nums.append(val)\n",
    "        return constructMaximumBinaryTree(nums)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if not nums:\n",
    "            return None\n",
    "    \n",
    "        # 找到数组中的最大值\n",
    "        maxVal = max(nums)\n",
    "        index = nums.index(maxVal)\n",
    "        \n",
    "        root = TreeNode(maxVal)\n",
    "        # 递归调用构造左右子树\n",
    "        root.left = self.constructMaximumBinaryTree(nums[:index])\n",
    "        root.right = self.constructMaximumBinaryTree(nums[index+1:])\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# [3,2,1,6,0,5]\n",
    "\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:\n",
    "        # 第一反应，递归，需要用dict记录index,如果用字典，就不能有重复的数字\n",
    "        # 看下题目，果然没有重复的数字\n",
    "        # construct 返回的应该是node\n",
    "\n",
    "        # 固定的字典，那传参数就是start,end\n",
    "        # 不固定的字段，那就是传列表，每次重新生成字典\n",
    "\n",
    "        self.d={}\n",
    "        for i,num in enumerate(nums):\n",
    "            self.d[num]=i\n",
    "\n",
    "        # [)\n",
    "        def construct(start,end):\n",
    "            # print(nums)\n",
    "            if not nums[start:end]:\n",
    "                return None\n",
    "            \n",
    "            val=max(nums[start:end])\n",
    "            i=self.d[val]\n",
    "            node=TreeNode(val)\n",
    "\n",
    "            node.left=construct(start,i)\n",
    "            node.right=construct(i+1,end)\n",
    "\n",
    "            # node.left=construct(nums[0:i])\n",
    "            # node.right=construct(nums[i+1:])\n",
    "\n",
    "            return node\n",
    "\n",
    "        node=construct(0,len(nums))\n",
    "\n",
    "        return node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        dic={val:index for index,val in enumerate(nums)}\n",
    "        print(dic)\n",
    "\n",
    "        def dfs(left,right):\n",
    "            if left>=right:\n",
    "                return \n",
    "            root_value=max(nums[left:right])\n",
    "            root=TreeNode(root_value)\n",
    "            index=dic[root_value]\n",
    "\n",
    "            root.left=dfs(left,index)\n",
    "            root.right=dfs(index+1,right)\n",
    "            return root\n",
    "\n",
    "        return dfs(0,len(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if not nums:\n",
    "            return None\n",
    "        a = max(nums)\n",
    "        b = nums.index(a)\n",
    "        root = TreeNode(a)\n",
    "        left_nums = nums[0:b]\n",
    "        right_nums = nums[b+1:]\n",
    "        root.left = self.constructMaximumBinaryTree(left_nums)\n",
    "        root.right = self.constructMaximumBinaryTree(right_nums)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        dic = {}\n",
    "        for i in range(len(nums)):\n",
    "            dic[nums[i]] = i\n",
    "        def dfs(left, right):\n",
    "            max_num = max(nums[left: right + 1])\n",
    "            max_index = dic[max_num]\n",
    "            root = TreeNode(max_num)\n",
    "            left_num = max_index - left\n",
    "            right_num = right - max_index\n",
    "            # print(max_num, left_num, right_num)\n",
    "            if left_num > 0:\n",
    "                root.left = dfs(left, max_index - 1)\n",
    "            if right_num > 0:\n",
    "                root.right = dfs(max_index + 1, right)\n",
    "            return root\n",
    "        return dfs(0, len(nums) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "  \n",
    "    def constructMaximumBinaryTree(self,nums: List[int]) -> Optional[TreeNode]:\n",
    "        if not nums:\n",
    "           return None\n",
    "        maxNums = max(nums)\n",
    "        index = nums.index(maxNums)\n",
    "        root = TreeNode(maxNums)\n",
    "        root.left = self.constructMaximumBinaryTree(nums[:index])\n",
    "        root.right = self.constructMaximumBinaryTree(nums[index+1:])\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        index = {item: i for i, item in enumerate(nums)}\n",
    "\n",
    "        def myTree(left, right):\n",
    "            if left == right:\n",
    "                return TreeNode(nums[left])\n",
    "            elif left > right:\n",
    "                return None\n",
    "\n",
    "            maxNum = max(nums[left: right + 1])\n",
    "            root = TreeNode(maxNum)\n",
    "            rootIndex = index[maxNum]\n",
    "            root.left = myTree(left, rootIndex - 1)\n",
    "            root.right = myTree(rootIndex + 1, right)\n",
    "\n",
    "            return root\n",
    "        \n",
    "        return myTree(0, len(nums) - 1)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "def func1(nums):\n",
    "    idx=0\n",
    "    max1=nums[0]\n",
    "    for i in range(len(nums)):\n",
    "        if nums[i]>max1:\n",
    "            max1=nums[i]\n",
    "            idx=i\n",
    "    return max1,idx\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if not  nums:\n",
    "            return None\n",
    "        max1,idx=func1(nums)\n",
    "        root=TreeNode(max1)\n",
    "        root.left=self.constructMaximumBinaryTree(nums[:idx])\n",
    "        root.right=self.constructMaximumBinaryTree(nums[idx+1:])\n",
    "        return root\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        nums_hash = {val: index for index, val in enumerate(nums)}\n",
    "        def construct(left_ptr, right_ptr):\n",
    "            if left_ptr > right_ptr:\n",
    "                return None\n",
    "            root_val = max(nums[left_ptr:right_ptr+1])\n",
    "            root = TreeNode(root_val)\n",
    "            pivot_id = nums_hash[root_val]\n",
    "            root.left = construct(left_ptr, pivot_id - 1)\n",
    "            root.right = construct(pivot_id + 1, right_ptr)\n",
    "            return root\n",
    "        return construct(0, len(nums) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if not nums:\n",
    "            return None\n",
    "        \n",
    "        # 找最大值及其下标\n",
    "        ind = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] > nums[ind]:\n",
    "                ind = i\n",
    "        root = TreeNode(nums[ind])\n",
    "        root.left = self.constructMaximumBinaryTree(nums[0: ind])\n",
    "        root.right = self.constructMaximumBinaryTree(nums[ind + 1:])\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if not nums:\n",
    "            return None\n",
    "        if len(nums) == 1:\n",
    "            return TreeNode(nums[0])\n",
    "        node = TreeNode(0)\n",
    "        maxValue = 0\n",
    "        maxValueIndex = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] > maxValue:\n",
    "                maxValue = nums[i]\n",
    "                maxValueIndex = i\n",
    "        node.val = maxValue\n",
    "        \n",
    "        if maxValueIndex > 0:\n",
    "            leftlist=nums[:maxValueIndex]\n",
    "            node.left=self.constructMaximumBinaryTree(leftlist)\n",
    "        if maxValueIndex < len(nums) - 1:\n",
    "            rightlist = nums[maxValueIndex + 1:]\n",
    "            node.right = self.constructMaximumBinaryTree(rightlist)\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if len(nums) == 1:\n",
    "            return TreeNode(nums[0])\n",
    "        max_val = 0\n",
    "        index = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] > max_val:\n",
    "                max_val = nums[i]\n",
    "                index = i\n",
    "\n",
    "        root = TreeNode(max_val)\n",
    "        if index > 0:\n",
    "            li = nums[:index]\n",
    "            left = self.constructMaximumBinaryTree(li)\n",
    "            root.left = left\n",
    "        if index < len(nums) - 1:\n",
    "            li = nums[index + 1:]\n",
    "            right = self.constructMaximumBinaryTree(li)    \n",
    "            root.right = right\n",
    "\n",
    "        return root\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if not nums:\n",
    "            return\n",
    "        root = TreeNode(max(nums))\n",
    "        idx = nums.index(max(nums))\n",
    "        root.left = self.constructMaximumBinaryTree(nums[:idx])\n",
    "        root.right = self.constructMaximumBinaryTree(nums[idx+1:])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if not nums:\n",
    "            return None\n",
    "        max_val = max(nums)\n",
    "        max_index = nums.index(max_val)\n",
    "        node = TreeNode(max_val)\n",
    "        node.left = self.constructMaximumBinaryTree(nums[:max_index])\n",
    "        node.right = self.constructMaximumBinaryTree(nums[max_index + 1:])\n",
    "        return node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if not nums:\n",
    "            return None\n",
    "        root_val = max(nums)\n",
    "        index = nums.index(root_val)\n",
    "        root = TreeNode(root_val)\n",
    "        root.left = self.constructMaximumBinaryTree(nums[: index])\n",
    "        root.right = self.constructMaximumBinaryTree(nums[index + 1: ])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if not nums:\n",
    "            return None\n",
    "        num = max(nums)\n",
    "        idx = nums.index(num)\n",
    "        return TreeNode(num, self.constructMaximumBinaryTree(nums[:idx]), self.constructMaximumBinaryTree(nums[idx + 1:]))\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if not nums:\n",
    "            return None\n",
    "        \n",
    "        root_val = max(nums)\n",
    "        root = TreeNode(root_val)\n",
    "\n",
    "        Tree_index = nums.index(root_val)\n",
    "\n",
    "        Tree_left = nums[:Tree_index]\n",
    "        Tree_right = nums[Tree_index + 1:]\n",
    "\n",
    "        root.left = self.constructMaximumBinaryTree(Tree_left)\n",
    "        root.right = self.constructMaximumBinaryTree(Tree_right)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        def buildTree(inputlst: list) -> TreeNode:\n",
    "            if not inputlst: return\n",
    "            # current root\n",
    "            curRoot = max(inputlst)\n",
    "            root = TreeNode(curRoot)\n",
    "            if len(inputlst) == 1: return root\n",
    "            # cut to left and right child\n",
    "            rootIdx = inputlst.index(curRoot)\n",
    "            leftlst = inputlst[:rootIdx]\n",
    "            rightlst = inputlst[rootIdx + 1:]\n",
    "\n",
    "            # construct left and right child\n",
    "            root.left = buildTree(leftlst)\n",
    "            root.right = buildTree(rightlst)\n",
    "\n",
    "            return root\n",
    "        return buildTree(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        # search_index = dict()\n",
    "        # sorted_nums = sorted(nums, key = lambda x: -x)\n",
    "        # for i, num in enumerate(sorted_nums):\n",
    "        #     search_index[num] = i\n",
    "        # root = TreeNode(val = sorted_nums[0])\n",
    "        # split = search_index[sorted_nums[0]]\n",
    "\n",
    "        def helper(nums, l, r):\n",
    "            # if len(nums) == 0:\n",
    "                # return \n",
    "            if l > r:\n",
    "                return\n",
    "            max_val = -float(\"inf\")\n",
    "            max_index = 0\n",
    "            # for i, num in enumerate(nums[l:r+1]):\n",
    "            #     if max_val < num:\n",
    "            #         max_index = i\n",
    "            i = l\n",
    "            while i <= r:\n",
    "                if max_val < nums[i]:\n",
    "                    max_index = i\n",
    "                    max_val = nums[i]\n",
    "                i += 1\n",
    "            root = TreeNode(val = nums[max_index])\n",
    "            left = helper(nums, l, max_index - 1)\n",
    "            right = helper(nums, max_index + 1, r)\n",
    "            root.left = left\n",
    "            root.right = right\n",
    "            # left = helper(root, nums[0:split], search_index[max(nums[0:split])])\n",
    "            return root\n",
    "        return helper(nums, 0, len(nums) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if not nums:\n",
    "            return None\n",
    "        # 1. 初始化根节点\n",
    "        root_val = max(nums)\n",
    "        root = TreeNode(root_val)\n",
    "        # 2. 切割nums\n",
    "        root_index = nums.index(root_val)\n",
    "        nums_left = nums[:root_index]\n",
    "        nums_right = nums[root_index + 1:]\n",
    "        # 3. 递归\n",
    "        root.left = self.constructMaximumBinaryTree(nums_left)\n",
    "        root.right = self.constructMaximumBinaryTree(nums_right)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        def dfs(nums):\n",
    "            if len(nums) == 0:\n",
    "                return None\n",
    "            root = TreeNode(max(nums))\n",
    "            index = nums.index(root.val)\n",
    "            root.left = dfs(nums[:index])\n",
    "            root.right = dfs(nums[index+1:])\n",
    "\n",
    "            return root\n",
    "        \n",
    "        root = dfs(nums)\n",
    "\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    \"\"\"递归法 更快\"\"\"\n",
    "\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:\n",
    "        if not nums:\n",
    "            return None\n",
    "        maxvalue = max(nums)\n",
    "        index = nums.index(maxvalue)\n",
    "\n",
    "        root = TreeNode(maxvalue)\n",
    "\n",
    "        left = nums[:index]\n",
    "        right = nums[index + 1:]\n",
    "\n",
    "        root.left = self.constructMaximumBinaryTree(left)\n",
    "        root.right = self.constructMaximumBinaryTree(right)\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if not nums:\n",
    "            return None\n",
    "        max_value = max(nums)\n",
    "        max_index = nums.index(max_value)\n",
    "        root = TreeNode(max_value)\n",
    "        nums_max_left = nums[:max_index]\n",
    "        nums_max_right = nums[max_index+1:]\n",
    "        root.left = self.constructMaximumBinaryTree(nums_max_left)\n",
    "        root.right = self.constructMaximumBinaryTree(nums_max_right)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "\n",
    "        if len(nums) == 0:\n",
    "            return None\n",
    "\n",
    "        root = TreeNode(max(nums))\n",
    "        i = nums.index(root.val)\n",
    "\n",
    "        root.left = self.constructMaximumBinaryTree(nums[:i])\n",
    "        root.right = self.constructMaximumBinaryTree(nums[i+1:])\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if not nums:\n",
    "            return\n",
    "        max_val = max(nums)\n",
    "        i = nums.index(max_val)\n",
    "        root = TreeNode(max_val)\n",
    "        nums = nums[:i] + nums[i+1:]\n",
    "        root.left = self.constructMaximumBinaryTree(nums[:i])\n",
    "        root.right = self.constructMaximumBinaryTree(nums[i:])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxtrree(self,nums,start,end):\n",
    "        if start == end:\n",
    "            return\n",
    "        maxindex = start\n",
    "        for i in range(start + 1,end):\n",
    "            if nums[i] > nums[maxindex]:\n",
    "                maxindex = i\n",
    "        root = TreeNode(nums[maxindex])\n",
    "        root.left = self.maxtrree(nums,start,maxindex)\n",
    "        root.right = self.maxtrree(nums,maxindex+1,end)\n",
    "        return root\n",
    "\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        return self.maxtrree(nums,0,len(nums))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def construct(self,nums):\n",
    "        if len(nums) == 1:\n",
    "            return TreeNode(nums[0])\n",
    "        max_index,max_val = 0,0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] > max_val:\n",
    "                max_index = i\n",
    "                max_val = nums[i]\n",
    "        node = TreeNode(max_val)\n",
    "        if max_index < len(nums) - 1:\n",
    "            node.right = self.construct(nums[max_index+1:])\n",
    "        if max_index > 0:\n",
    "            node.left = self.construct(nums[:max_index])\n",
    "        return node\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if len(nums) == 0:\n",
    "            return None\n",
    "        return  self.construct(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        \n",
    "        if not nums:\n",
    "            return None\n",
    "            \n",
    "        max_val = max(nums)\n",
    "        index = nums.index(max_val)\n",
    "        \n",
    "        node = TreeNode(val=max_val)\n",
    "\n",
    "        nums_left = nums[:index]\n",
    "        nums_right = nums[index+1:]\n",
    "\n",
    "        node.left = self.constructMaximumBinaryTree(nums_left)\n",
    "        node.right = self.constructMaximumBinaryTree(nums_right)\n",
    "\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if not nums:\n",
    "            return None\n",
    "        mx = max(nums)\n",
    "        p = nums.index(mx)\n",
    "        l = nums[:p]\n",
    "        r = nums[p+1:]\n",
    "        return TreeNode(mx, self.constructMaximumBinaryTree(l), self.constructMaximumBinaryTree( r))\n",
    "        \n",
    "        # def run(nums):\n",
    "        #     mx = max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if not nums:\n",
    "            return None\n",
    "        max_idx = nums.index(max(nums))\n",
    "        root = TreeNode(nums[max_idx])\n",
    "        root.left = self.constructMaximumBinaryTree(nums[:max_idx])\n",
    "        root.right = self.constructMaximumBinaryTree(nums[max_idx+1:])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "'''\n",
    "#digui\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "\n",
    "        def digui(nums):\n",
    "            if not len(nums):\n",
    "                return None\n",
    "            if len(nums) == 1:\n",
    "                return TreeNode(nums.pop(),None,None)\n",
    "            maxval = max(nums)\n",
    "            maxpos = nums.index(maxval)\n",
    "            p = TreeNode(maxval,None,None)\n",
    "            p.left = digui(nums[:maxpos])\n",
    "            p.right = digui(nums[maxpos+1:])\n",
    "            return p\n",
    "        \n",
    "        return digui(nums)\n",
    "'''\n",
    "#单调栈\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        p = TreeNode(nums[0])\n",
    "        zhan = [p]\n",
    "        for i in range(1,len(nums)):\n",
    "            p = TreeNode(nums[i])\n",
    "            if nums[i] < zhan[-1].val:\n",
    "                zhan[-1].right = p\n",
    "\n",
    "            else:\n",
    "                while zhan and nums[i] > zhan[-1].val:\n",
    "                    p.left = zhan.pop()\n",
    "                if zhan:\n",
    "                    zhan[-1].right = p\n",
    "            zhan.append(p)\n",
    "        return zhan[0]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if not nums:\n",
    "            return None\n",
    "        max_num = max(nums)\n",
    "        max_index = nums.index(max_num)\n",
    "        node = TreeNode(val=max_num)\n",
    "\n",
    "        node.left = self.constructMaximumBinaryTree(nums[:max_index])\n",
    "        node.right = self.constructMaximumBinaryTree(nums[max_index+1:])\n",
    "\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if len(nums) == 0:\n",
    "            return None\n",
    "        maxVal = 0\n",
    "        maxValIdx = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if num >= maxVal:\n",
    "                maxValIdx = i\n",
    "                maxVal = num\n",
    "        node = TreeNode(val=maxVal)\n",
    "        node.left = self.constructMaximumBinaryTree(nums[:maxValIdx])\n",
    "        node.right = self.constructMaximumBinaryTree(nums[maxValIdx+1:])\n",
    "        return node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if not nums:\n",
    "            return None\n",
    "        root = TreeNode(max(nums))\n",
    "        idx = nums.index(max(nums))\n",
    "        root.left = self.constructMaximumBinaryTree(nums[:idx])\n",
    "        root.right = self.constructMaximumBinaryTree(nums[idx + 1:])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if len(nums)==1:\n",
    "            return TreeNode(nums[0])\n",
    "        if len(nums)==0:\n",
    "            return None\n",
    "        maximum=max(nums)\n",
    "        maximum_idx=nums.index(maximum)\n",
    "        root=TreeNode(maximum)\n",
    "        root.left=self.constructMaximumBinaryTree(nums[:maximum_idx])\n",
    "        root.right=self.constructMaximumBinaryTree(nums[maximum_idx+1:])\n",
    "        return root\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if not nums:\n",
    "            return None\n",
    "        max_idx = 0\n",
    "        max_val = 0\n",
    "        for idx, num in enumerate(nums):\n",
    "            if num > max_val:\n",
    "                max_val = num\n",
    "                max_idx = idx\n",
    "        root = TreeNode(max_val)\n",
    "        root.left = self.constructMaximumBinaryTree(nums[:max_idx])\n",
    "        root.right = self.constructMaximumBinaryTree(nums[max_idx+1:])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "# https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-66994/dong-ge-da-172f0/\n",
    "# 二叉树的构造问题一般都是使用「分解问题」的思路：构造整棵树 = 根节点 + 构造左子树 + 构造右子树。\n",
    "# 题目意思，数组里面的相对位置顺序很重要的\n",
    "# 方法一：\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if not nums:\n",
    "            return None\n",
    "        \n",
    "        # 找到数组中的最大值\n",
    "        max_val = max(nums)\n",
    "        max_val_idx = nums.index(max_val)\n",
    "\n",
    "        root = TreeNode(max_val)\n",
    "        # 递归调用构造左右子树\n",
    "        root.left = self.constructMaximumBinaryTree(nums[:max_val_idx])\n",
    "        root.right = self.constructMaximumBinaryTree(nums[max_val_idx+1:])\n",
    "\n",
    "        return root\n",
    "\n",
    "# 方法二：上述方法优化下,搞的更加通用一点，从nums的任意位置处，用前序遍历的方式都可以构造二叉树\n",
    "# class Solution:\n",
    "#     def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "#         if not nums:\n",
    "#             return None\n",
    "\n",
    "#         l, r = 0, len(nums) - 1\n",
    "#         return self.build(nums, l, r)\n",
    "    \n",
    "#     def build(self, nums, l, r):\n",
    "#         if l > r:\n",
    "#             return None\n",
    "        \n",
    "#         max_val = max(nums[l:r+1])\n",
    "#         max_index = nums.index(max_val)\n",
    "\n",
    "#         root = TreeNode(max_val)\n",
    "#         # 递归调用构造左右子树\n",
    "#         root.left = self.build(nums, l, max_index-1)\n",
    "#         root.right = self.build(nums, max_index+1, r)\n",
    "\n",
    "#         return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if len(nums)==1:\n",
    "            return TreeNode(nums[0])\n",
    "        \n",
    "        max_id = 0\n",
    "        max_value = nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] > max_value:\n",
    "                max_id = i\n",
    "                max_value = nums[i]\n",
    " \n",
    "        new_node = TreeNode(max_value)\n",
    "        if len(nums[:max_id])>0:\n",
    "            new_node.left = self.constructMaximumBinaryTree(nums[:max_id])\n",
    "        if len(nums[max_id+1:])>0:\n",
    "            new_node.right = self.constructMaximumBinaryTree(nums[max_id+1:])\n",
    "        \n",
    "        return new_node\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def get_max_index(self, lst:list) -> int:\n",
    "        j = 0\n",
    "        for i in range(1,len(lst)):\n",
    "            if lst[i]>lst[j]:\n",
    "                j = i\n",
    "        return j\n",
    "    def dfs(self, lst:list) -> TreeNode:\n",
    "        if not lst:\n",
    "            return None\n",
    "        idx = self.get_max_index(lst)\n",
    "        node = TreeNode(lst[idx])\n",
    "        node.left = self.dfs(lst[:idx])\n",
    "        node.right = self.dfs(lst[idx+1:])\n",
    "        return node\n",
    "\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        return self.dfs(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:\n",
    "        if not nums:\n",
    "            return None\n",
    "        max_val = max(nums)\n",
    "        max_index = nums.index(max_val)\n",
    "        node = TreeNode(max_val)\n",
    "        node.left = self.constructMaximumBinaryTree(nums[:max_index])\n",
    "        node.right = self.constructMaximumBinaryTree(nums[max_index + 1:])\n",
    "        return node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if not nums:\n",
    "            return None\n",
    "        max_val = max(nums)\n",
    "        max_index = nums.index(max_val)\n",
    "        node = TreeNode(max_val)\n",
    "        node.left = self.constructMaximumBinaryTree(nums[:max_index])\n",
    "        node.right = self.constructMaximumBinaryTree(nums[max_index+1:])\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        return self.build(nums, 0, len(nums) - 1)\n",
    "\n",
    "\n",
    "    def build(self, nums, left, right):\n",
    "        if left > right:\n",
    "            return\n",
    "        \n",
    "        index, max_val = -1, -float('inf')\n",
    "        for i in range(left, right+1):\n",
    "            if nums[i] > max_val:\n",
    "                index = i\n",
    "                max_val = nums[i]\n",
    "        \n",
    "        node = TreeNode(max_val)\n",
    "        node.left = self.build(nums, left, index-1)\n",
    "        node.right = self.build(nums, index+1, right)\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if not nums:\n",
    "            return None\n",
    "        val = max(nums)\n",
    "        i = nums.index(val)\n",
    "\n",
    "        node = TreeNode(val)\n",
    "\n",
    "        left = nums[:i]\n",
    "        right = nums[i+1:]\n",
    "\n",
    "        node.left = self.constructMaximumBinaryTree(left)\n",
    "        node.right = self.constructMaximumBinaryTree(right)\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:      \n",
    "        def back(n):\n",
    "            if not n:\n",
    "                return None\n",
    "            point = max(n)\n",
    "            root = TreeNode(point)\n",
    "            point_idx = n.index(point)\n",
    "            nums_left = n[:point_idx]\n",
    "            root.left = back(nums_left)\n",
    "            nums_right = n[point_idx+1:]\n",
    "            root.right = back(nums_right)\n",
    "            return root\n",
    "        return back(nums)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if not nums:\n",
    "            return\n",
    "        \n",
    "        root_val = max(nums)\n",
    "        sep_idx = nums.index(root_val)\n",
    "        root = TreeNode(root_val)\n",
    "        root.left = self.constructMaximumBinaryTree(nums[:sep_idx])\n",
    "        root.right = self.constructMaximumBinaryTree(nums[sep_idx+1:])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if len(nums) == 0:\n",
    "            return None\n",
    "        if len(nums) == 1:\n",
    "            return TreeNode(nums[0])    # 只剩一个节点的时候返回节点\n",
    "        \n",
    "        maxval = max(nums)\n",
    "        maxval_index = nums.index(maxval)   # 取最大值的索引\n",
    "        root = TreeNode(maxval)\n",
    "        root.left = self.constructMaximumBinaryTree(nums[:maxval_index])\n",
    "        root.right = self.constructMaximumBinaryTree(nums[maxval_index+1:])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        max_val = max(nums)\n",
    "        root = TreeNode(max_val)\n",
    "        max_index = nums.index(max_val)\n",
    "        #root = TreeNode(max_val)\n",
    "\n",
    "        \n",
    "        left_nums = nums[:max_index]\n",
    "        right_nums = nums[max_index + 1:]\n",
    "\n",
    "        if left_nums:\n",
    "            root.left = self.constructMaximumBinaryTree(left_nums)\n",
    "        if right_nums:\n",
    "            root.right = self.constructMaximumBinaryTree(right_nums)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if len(nums) == 0:\n",
    "            return None\n",
    "        value = max(nums)\n",
    "        root = TreeNode(value)\n",
    "        index = nums.index(value)\n",
    "        leftnums = nums[:index]\n",
    "        rightnums = nums[index+1:]\n",
    "        root.left = self.constructMaximumBinaryTree(leftnums)\n",
    "        root.right = self.constructMaximumBinaryTree(rightnums)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if len(nums) == 0:\n",
    "            return None\n",
    "            \n",
    "        root_val = max(nums)\n",
    "        index = nums.index(root_val)\n",
    "\n",
    "        root = TreeNode(root_val)\n",
    "\n",
    "        root.left = self.constructMaximumBinaryTree(nums[:index])\n",
    "        root.right = self.constructMaximumBinaryTree(nums[index + 1:])\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def traversal(self, nums):\n",
    "        # rootValue = float('-inf')\n",
    "        # index = -1\n",
    "        # for i in range(len(nums)):\n",
    "        #     if rootValue < nums[i]:\n",
    "        #         rootValue = nums[i]\n",
    "        #         index = i\n",
    "        if not nums:\n",
    "            return None\n",
    "        rootValue = max(nums)\n",
    "        rootIndex = nums.index(rootValue)\n",
    "        root = TreeNode(rootValue)\n",
    "        root.left = self.traversal(nums[:rootIndex])\n",
    "        root.right = self.traversal(nums[rootIndex + 1:])\n",
    "\n",
    "        return root\n",
    "\n",
    "\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if not nums:\n",
    "            return None\n",
    "        root = self.traversal(nums)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        return self.transfer(nums, 0, len(nums))\n",
    "    \n",
    "    def transfer(self, nums: List[int], start: int, end: int) -> Optional[TreeNode]:\n",
    "        if start >= end:\n",
    "            return None\n",
    "        # max_index = nums.index(max(nums[start:end]))\n",
    "        max_index = start\n",
    "        for i in range(start + 1, end):\n",
    "            if nums[i] > nums[max_index]:\n",
    "                max_index = i\n",
    "\n",
    "        root = TreeNode(nums[max_index])\n",
    "        root.left = self.transfer(nums, start, max_index)\n",
    "        root.right = self.transfer(nums, max_index+1, end)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if not nums:\n",
    "            return\n",
    "        rootVal = max(nums)\n",
    "        rootIndex = nums.index(rootVal)\n",
    "        root = TreeNode(val = rootVal)\n",
    "        root.left = self.constructMaximumBinaryTree(nums[:rootIndex])\n",
    "        root.right = self.constructMaximumBinaryTree(nums[rootIndex + 1:])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "\n",
    "        if len(nums) < 1:\n",
    "            return None\n",
    "\n",
    "        elif len(nums) == 1:\n",
    "            return TreeNode(nums[0])\n",
    "\n",
    "        max_ele = max(nums)\n",
    "        max_index = nums.index(max_ele)\n",
    "\n",
    "        left_nums = nums[:max_index]\n",
    "        right_nums = nums[max_index + 1:]\n",
    "\n",
    "        root = TreeNode(max_ele)\n",
    "\n",
    "        if len(left_nums) > 0:\n",
    "            root.left = self.constructMaximumBinaryTree(left_nums)\n",
    "\n",
    "        if len(right_nums) > 0:\n",
    "            root.right = self.constructMaximumBinaryTree(right_nums)\n",
    "\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if nums == []:\n",
    "            return None\n",
    "        \n",
    "        max_value = max(nums)\n",
    "        max_index = nums.index(max_value)\n",
    "        newnode = TreeNode(max_value)\n",
    "        newnode.left = self.constructMaximumBinaryTree(nums[:max_index])\n",
    "        newnode.right = self.constructMaximumBinaryTree(nums[max_index+1:])\n",
    "\n",
    "        return newnode\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        return self.transfer(nums, 0, len(nums))\n",
    "    \n",
    "    def transfer(self, nums: List[int], start: int, end: int) -> Optional[TreeNode]:\n",
    "        if start >= end:\n",
    "            return None\n",
    "        max_index = nums.index(max(nums[start:end]))\n",
    "        # max_index = start\n",
    "        # for i in range(start + 1, end):\n",
    "        #     if nums[i] > nums[max_index]:\n",
    "        #         max_index = i\n",
    "\n",
    "        root = TreeNode(nums[max_index])\n",
    "        root.left = self.transfer(nums, start, max_index)\n",
    "        root.right = self.transfer(nums, max_index+1, end)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        def constructMaximumBinaryTreeHelp(left,right):\n",
    "            if left >= right:\n",
    "                return \n",
    "            val = max(nums[left:right])\n",
    "            index = nums.index(val)\n",
    "            root = TreeNode(val = val)\n",
    "            root.left = constructMaximumBinaryTreeHelp(left,index)\n",
    "            root.right = constructMaximumBinaryTreeHelp(index+1,right)\n",
    "            return root\n",
    "        return constructMaximumBinaryTreeHelp(0,len(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getMaxNum(self, start, end):\n",
    "        idx = start\n",
    "        for i in range(start+1, end+1):\n",
    "            if self.nums[i] > self.nums[idx]:\n",
    "                idx = i\n",
    "        return idx\n",
    "\n",
    "    def constructPartTree(self, start, end): # 包含左右子节点\n",
    "        if start > end:\n",
    "            return None\n",
    "        idx = self.getMaxNum(start, end)\n",
    "        node = TreeNode(self.nums[idx])\n",
    "        if idx > start: node.left = self.constructPartTree(start, idx-1) \n",
    "        if idx < end: node.right = self.constructPartTree(idx+1, end)\n",
    "        return node\n",
    "    \n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        self.nums = nums\n",
    "        return self.constructPartTree(0, len(nums)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if not nums:\n",
    "            return None\n",
    "        max_value = max(nums)\n",
    "        max_index = nums.index(max_value)\n",
    "        root = TreeNode(max_value)\n",
    "        root.left = self.constructMaximumBinaryTree(nums[:max_index])\n",
    "        root.right = self.constructMaximumBinaryTree(nums[max_index+1:])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        # 3. stop\n",
    "        if len(nums)==0:\n",
    "            return None\n",
    "\n",
    "        # 2. every step\n",
    "        # 找到节点\n",
    "        rootval = max(nums) \n",
    "        root = TreeNode(rootval)\n",
    "        idx = nums.index(rootval)\n",
    "        nums_left = nums[:idx]\n",
    "        nums_right = nums[idx+1:]\n",
    "        # 定义该节点的左右\n",
    "        root.left = self.constructMaximumBinaryTree(nums_left)\n",
    "        root.right = self.constructMaximumBinaryTree(nums_right)\n",
    "\n",
    "        #1. return. return节点，并定义该节点的左右\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if len(nums)==1:\n",
    "            return TreeNode(nums[0])\n",
    "        rootValue=max(nums)\n",
    "        rootIndex=nums.index(rootValue)\n",
    "        \n",
    "        right=nums[1+rootIndex:len(nums)]\n",
    "        node=TreeNode(rootValue)\n",
    "        if rootIndex>0:\n",
    "            left_nums = nums[0:rootIndex]\n",
    "            node.left=self.constructMaximumBinaryTree(left_nums)\n",
    "        if rootIndex<len(nums)-1:\n",
    "            right_nums = nums[1 + rootIndex:len(nums)]\n",
    "            node.right=self.constructMaximumBinaryTree(right_nums)\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if not nums:\n",
    "            return None\n",
    "        if len(nums) == 1:\n",
    "            return TreeNode(nums[0])\n",
    "        i, x = -1, -1\n",
    "        for k, v in enumerate(nums):\n",
    "            if v > x:\n",
    "                i = k\n",
    "                x = v\n",
    "        root = TreeNode(x)\n",
    "        root.left = self.constructMaximumBinaryTree(nums[:i])\n",
    "        root.right = self.constructMaximumBinaryTree(nums[i+1:])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        def build(nums):\n",
    "            if not nums:\n",
    "                return None\n",
    "\n",
    "            max_value = max(nums)\n",
    "            max_index = nums.index(max_value)\n",
    "\n",
    "            root = TreeNode(max_value)\n",
    "            root.left = build(nums[:max_index])\n",
    "            root.right = build(nums[max_index + 1:])\n",
    "            return root\n",
    "\n",
    "        return build(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if not nums:\n",
    "            return []\n",
    "        root = TreeNode(max(nums))\n",
    "        if len(nums)==1:\n",
    "            return root\n",
    "        #存在子树\n",
    "        seg_id = nums.index(max(nums))\n",
    "        if seg_id>0:#存在左子树\n",
    "            root.left = self.constructMaximumBinaryTree(nums[:seg_id])\n",
    "        if seg_id<len(nums)-1:#存在右子树\n",
    "            root.right = self.constructMaximumBinaryTree(nums[seg_id+1:])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        result =self.build(nums,0,len(nums))\n",
    "        return result\n",
    "    def build(self,nums,left,right):\n",
    "        if left>=right:\n",
    "            return None\n",
    "        if right-left==1:\n",
    "            node=TreeNode(nums[left])\n",
    "            return node\n",
    "        # 构造二叉树，一般都是前序\n",
    "        temp=max(nums[left:right])\n",
    "        idx=nums.index(temp)\n",
    "        root=TreeNode(temp)\n",
    "        root.left=self.build(nums,left,idx)\n",
    "        root.right=self.build(nums,idx+1,right)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "\n",
    "        #用前序遍历的方式\n",
    "\n",
    "        #递归第二步:\n",
    "        if nums == []: #nums长度越来越小，一定会为[]\n",
    "            return None\n",
    "\n",
    "        #这里如果再写一个长度为1的判断的话，其实是做的剪枝，剪枝的都是对[]的剪枝\n",
    "\n",
    "        #处理单层逻辑\n",
    "        #用前序遍历的方式\n",
    "        max_num = max(nums)\n",
    "        max_index = nums.index(max_num)\n",
    "\n",
    "        #前序遍历，先构造节点\n",
    "        left_tree = self.constructMaximumBinaryTree(nums[:max_index])\n",
    "        right_tree = self.constructMaximumBinaryTree(nums[max_index+1:])\n",
    "        new_node  = TreeNode(max_num, left_tree,right_tree)\n",
    "\n",
    "        return new_node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if len(nums) == 0:\n",
    "            return None\n",
    "        if len(nums) == 1:\n",
    "            return TreeNode(nums[0])\n",
    "        node = TreeNode()\n",
    "        maxval = -float('inf')\n",
    "        maxloc = -1\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] > maxval:\n",
    "                maxval = nums[i]\n",
    "                maxloc = i\n",
    "        node.val = maxval\n",
    "        node.left = self.constructMaximumBinaryTree(nums[:maxloc])\n",
    "        node.right = self.constructMaximumBinaryTree(nums[maxloc+1:])\n",
    "        return node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\r\n",
    "        if not nums:\r\n",
    "            return None\r\n",
    "        max_num = max(nums)\r\n",
    "        max_index = nums.index(max_num)\r\n",
    "        node = TreeNode(max_num)\r\n",
    "        node.left = self.constructMaximumBinaryTree(nums[:max_index])\r\n",
    "        node.right = self.constructMaximumBinaryTree(nums[max_index+1:])\r\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums):\n",
    "        if not nums:\n",
    "            return None\n",
    "        max_val=max(nums)\n",
    "        max_index=nums.index(max_val)\n",
    "        root=TreeNode(max_val)\n",
    "        root.left=self.constructMaximumBinaryTree(nums[:max_index])\n",
    "        root.right=self.constructMaximumBinaryTree(nums[max_index+1:])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        # 肯定是递归\n",
    "        if len(nums) == 0:\n",
    "            return None\n",
    "        return self.build(0, len(nums) - 1, nums)\n",
    "    def build(self, start, end, nums):\n",
    "        maxNumIndex = self.getMax(nums, start, end)\n",
    "        root = TreeNode(nums[maxNumIndex])\n",
    "        leftLen = maxNumIndex - start\n",
    "        rightLen = end - maxNumIndex\n",
    "        if leftLen == 1:\n",
    "            root.left = TreeNode(nums[start])\n",
    "            root.left.left, root.left.right = None, None\n",
    "        elif leftLen == 0:\n",
    "            root.left = None\n",
    "        else:\n",
    "            left = self.build(start, maxNumIndex - 1, nums)\n",
    "            root.left = left\n",
    "        if rightLen == 1:\n",
    "            root.right = TreeNode(nums[end])\n",
    "            root.right.left, root.right.right = None, None\n",
    "        elif rightLen == 0:\n",
    "            root.right = None\n",
    "        else:\n",
    "            right = self.build(maxNumIndex + 1, end, nums)\n",
    "            root.right = right\n",
    "        return root\n",
    "\n",
    "\n",
    "    def getMax(self, nums, left, right):\n",
    "        index = left\n",
    "        max = nums[left]\n",
    "        while left <= right:\n",
    "            if max < nums[left]:\n",
    "                index = left\n",
    "                max = nums[left]\n",
    "            left += 1\n",
    "        return index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if not nums:\n",
    "            return None\n",
    "\n",
    "        root_val = max(nums)\n",
    "        root = TreeNode(root_val)\n",
    "        \n",
    "        ind = nums.index(root_val)\n",
    "        num_left = nums[:ind]\n",
    "        num_right = nums[ind+1:]\n",
    "\n",
    "        root.left = self.constructMaximumBinaryTree(num_left)\n",
    "        root.right = self.constructMaximumBinaryTree(num_right)\n",
    "\n",
    "        return root\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        # 肯定是递归\n",
    "        return self.build(0, len(nums) - 1, nums)\n",
    "    def build(self, start, end, nums):\n",
    "        maxNumIndex = self.getMax(nums, start, end)\n",
    "        root = TreeNode(nums[maxNumIndex])\n",
    "        leftLen = maxNumIndex - start\n",
    "        rightLen = end - maxNumIndex\n",
    "        if leftLen == 1:\n",
    "            root.left = TreeNode(nums[start])\n",
    "            root.left.left, root.left.right = None, None\n",
    "        elif leftLen == 0:\n",
    "            root.left = None\n",
    "        else:\n",
    "            left = self.build(start, maxNumIndex - 1, nums)\n",
    "            root.left = left\n",
    "        if rightLen == 1:\n",
    "            root.right = TreeNode(nums[end])\n",
    "            root.right.left, root.right.right = None, None\n",
    "        elif rightLen == 0:\n",
    "            root.right = None\n",
    "        else:\n",
    "            right = self.build(maxNumIndex + 1, end, nums)\n",
    "            root.right = right\n",
    "        return root\n",
    "\n",
    "\n",
    "    def getMax(self, nums, left, right):\n",
    "        index = left\n",
    "        max = nums[left]\n",
    "        while left <= right:\n",
    "            if max < nums[left]:\n",
    "                index = left\n",
    "                max = nums[left]\n",
    "            left += 1\n",
    "        return index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        def construct(left: int, right: int) -> Optional[TreeNode]:\n",
    "            if left > right:\n",
    "                return None\n",
    "            \n",
    "            best = left\n",
    "            for i in range(left + 1, right + 1):\n",
    "                if nums[i] > nums[best]:\n",
    "                    best = i\n",
    "        \n",
    "            node = TreeNode(nums[best])\n",
    "            node.left = construct(left, best - 1)\n",
    "            node.right = construct(best + 1, right)\n",
    "            return node\n",
    "        \n",
    "        return construct(0, len(nums) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        if len(nums)==0:\n",
    "            return None\n",
    "        #构建新的根节点\n",
    "        root = TreeNode(0)\n",
    "        #找到数组中的最大值\n",
    "        index = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]>root.val:\n",
    "                root.val = nums[i]\n",
    "                index = i\n",
    "\n",
    "        #分割左区间\n",
    "        left = nums[:index]\n",
    "        #分割右区间\n",
    "        right = nums[index+1:]\n",
    "        #递归继续求解\n",
    "        root.left = self.constructMaximumBinaryTree(left)\n",
    "        root.right = self.constructMaximumBinaryTree(right)\n",
    "\n",
    "        return root\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "import re\r\n",
    "\r\n",
    "\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def build(self, nums, left, right):\r\n",
    "        if left > right:\r\n",
    "            return None\r\n",
    "        maxVal = max(nums[left:right+1])\r\n",
    "        maxIndex = nums.index(maxVal)\r\n",
    "        root = TreeNode(maxVal)\r\n",
    "\r\n",
    "        root.left = self.build(nums, left, maxIndex-1)\r\n",
    "        root.right = self.build(nums, maxIndex+1, right)\r\n",
    "        return root\r\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\r\n",
    "        return self.build(nums, 0, len(nums)-1)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "# 自己写的\n",
    "# 小结：构建一个树，用递归，return节点，并定义该节点的左右。\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        # 3. stop\n",
    "        if len(nums)==0:\n",
    "            return None\n",
    "\n",
    "        # 2. every step\n",
    "        # 找到节点\n",
    "        rootval = max(nums) \n",
    "        root = TreeNode(rootval)\n",
    "        idx = nums.index(rootval)\n",
    "        nums_left = nums[:idx]\n",
    "        nums_right = nums[idx+1:]\n",
    "        # 定义该节点的左右\n",
    "        root.left = self.constructMaximumBinaryTree(nums_left)\n",
    "        root.right = self.constructMaximumBinaryTree(nums_right)\n",
    "\n",
    "        #1. return. return节点，并定义该节点的左右\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        def dfs(left,right):\n",
    "            nonlocal nums\n",
    "            if left>right:\n",
    "                return None\n",
    "            if left==right:\n",
    "                return TreeNode(nums[left])\n",
    "            m = nums[left]\n",
    "            midx = left\n",
    "            for i in range(left+1,right+1):\n",
    "                if nums[i]>m:\n",
    "                    m = nums[i]\n",
    "                    midx = i \n",
    "            l = dfs(left, midx-1)\n",
    "            r = dfs(midx+1, right)\n",
    "            node = TreeNode(m, l, r)\n",
    "            return node\n",
    "        return dfs(0, len(nums)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        def construct(left: int, right: int) -> Optional[TreeNode]:\n",
    "            if left > right:\n",
    "                return None\n",
    "            \n",
    "            best = left\n",
    "            for i in range(left + 1, right + 1):\n",
    "                if nums[i] > nums[best]:\n",
    "                    best = i\n",
    "        \n",
    "            node = TreeNode(nums[best])\n",
    "            node.left = construct(left, best - 1)\n",
    "            node.right = construct(best + 1, right)\n",
    "            return node\n",
    "        \n",
    "        return construct(0, len(nums) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\r\n",
    "        L=len(nums)\r\n",
    "        stk=[]\r\n",
    "        left=[-1]*L\r\n",
    "        right=[-1]*L\r\n",
    "        for i in range(L):\r\n",
    "            while stk and nums[i]>nums[stk[-1]]:\r\n",
    "                right[stk[-1]]=i\r\n",
    "                stk.pop()\r\n",
    "            if stk:\r\n",
    "                left[i]=stk[-1]\r\n",
    "            stk.append(i)\r\n",
    "        \r\n",
    "        nodes=[TreeNode(val) for val in nums]\r\n",
    "        root=None\r\n",
    "        for i in range(L):\r\n",
    "            if left[i]==right[i]:\r\n",
    "                root=nodes[i]\r\n",
    "                continue\r\n",
    "            if right[i]==-1 or (left[i]!=-1 and nums[left[i]]<nums[right[i]]):\r\n",
    "                nodes[left[i]].right=nodes[i]\r\n",
    "            else:\r\n",
    "                nodes[right[i]].left=nodes[i]\r\n",
    "        return root\r\n",
    "        \r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "        def construct(left,right):\n",
    "            if left>right:\n",
    "                return None\n",
    "            \n",
    "            best=left\n",
    "            for i in range(left+1,right+1):\n",
    "                if nums[i]>nums[best]:\n",
    "                    best=i\n",
    "            \n",
    "            node=TreeNode(nums[best])\n",
    "            node.left=construct(left,best-1)\n",
    "            node.right=construct(best+1,right)\n",
    "            return node\n",
    "        \n",
    "        return construct(0,len(nums)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "        def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "\n",
    "            def dfs(start, end):\n",
    "                if start >= end:\n",
    "                    return None\n",
    "                else:\n",
    "                    maxIndex = searchMaxIndex(start, end)\n",
    "                    value = nums[maxIndex]\n",
    "                    node = TreeNode(value)\n",
    "                    node.left = dfs(start, maxIndex)\n",
    "                    node.right = dfs(maxIndex+1, end)\n",
    "                    return node\n",
    "\n",
    "            # 搜索最大的索引\n",
    "            def searchMaxIndex(start, end):\n",
    "                maxIndex = start\n",
    "                maxValue = nums[start]\n",
    "                for index in range(start, end):\n",
    "                    if nums[index] > maxValue:\n",
    "                        maxIndex = index\n",
    "                        maxValue = nums[maxIndex]\n",
    "                return maxIndex\n",
    "\n",
    "\n",
    "\n",
    "            N = len(nums)\n",
    "            m = dfs(0, N)\n",
    "            return m"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
